Proof by contraction is where a statement is assumed to be false, then a contradiction is found, showing that the original statement must be true.
Proof of the irrationality of
Assume that is rational, so for some integers , , where and are coprime.
Squaring gives , so .
Because , is even, so itself is even.
If is even, then for some integer .
Then, , so .
Because , is even, so itself is even.
and are both even, but this contradicts the assumption that and are coprime, as they both share a factor of 2. Thus, the assumption must be false, so is irrational.
Proof of the infinity of primes
Assume that there is a finite list of primes, so there is a largest prime number .
Consider multiplying all the prime numbers together, .
Consider . As it is 1 more than a multiple of every prime, it is not divisible by any prime (dividing by any prime leaves a remainder of 1).
Thus, is either prime, or divisible by a prime larger than (all numbers are either prime or have prime factors).
This contradicts the assumption that there are a finite number of primes, as there is some prime number larger than . Thus, the assumption must be false, so there are an infinite number of primes.